{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Alphabet Board Path"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: alphabetBoardPath"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #字母板上的路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>我们从一块字母板上的位置&nbsp;<code>(0, 0)</code>&nbsp;出发，该坐标对应的字符为&nbsp;<code>board[0][0]</code>。</p>\n",
    "\n",
    "<p>在本题里，字母板为<code>board = [\"abcde\", \"fghij\", \"klmno\", \"pqrst\", \"uvwxy\", \"z\"]</code>，如下所示。</p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/07/28/azboard.png\" style=\"width: 300px;\" /></p>\n",
    "\n",
    "<p>我们可以按下面的指令规则行动：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果方格存在，<code>'U'</code>&nbsp;意味着将我们的位置上移一行；</li>\n",
    "\t<li>如果方格存在，<code>'D'</code>&nbsp;意味着将我们的位置下移一行；</li>\n",
    "\t<li>如果方格存在，<code>'L'</code>&nbsp;意味着将我们的位置左移一列；</li>\n",
    "\t<li>如果方格存在，<code>'R'</code>&nbsp;意味着将我们的位置右移一列；</li>\n",
    "\t<li><code>'!'</code>&nbsp;会把在我们当前位置 <code>(r, c)</code> 的字符&nbsp;<code>board[r][c]</code>&nbsp;添加到答案中。</li>\n",
    "</ul>\n",
    "\n",
    "<p>（注意，字母板上只存在有字母的位置。）</p>\n",
    "\n",
    "<p>返回指令序列，用最小的行动次数让答案和目标&nbsp;<code>target</code>&nbsp;相同。你可以返回任何达成目标的路径。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>target = \"leet\"\n",
    "<strong>输出：</strong>\"DDR!UURRR!!DDD!\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>target = \"code\"\n",
    "<strong>输出：</strong>\"RR!DDRR!UUL!R!\"\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= target.length &lt;= 100</code></li>\n",
    "\t<li><code>target</code>&nbsp;仅含有小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [alphabet-board-path](https://leetcode.cn/problems/alphabet-board-path/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [alphabet-board-path](https://leetcode.cn/problems/alphabet-board-path/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"leet\"', '\"code\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        #将每一个位置都坐标化，初始坐标是(0,0)\n",
    "        locx=0\n",
    "        locy=0\n",
    "        res=\"\"\n",
    "        for i in target:\n",
    "            #求得目标位置的坐标\n",
    "            temp=ord(i)-ord('a')\n",
    "            targetx=temp%5\n",
    "            targety=temp//5\n",
    "            if targetx<locx:\n",
    "                res+='L'*(locx-targetx)\n",
    "                if targety<locy:\n",
    "                    res+='U'*(locy-targety)\n",
    "                else:\n",
    "                    res+='D'*(targety-locy)\n",
    "            else:\n",
    "                if targety<locy:\n",
    "                    res+='U'*(locy-targety)\n",
    "                else:\n",
    "                    res+='D'*(targety-locy)\n",
    "                res+='R'*(targetx-locx)\n",
    "            locx=targetx\n",
    "            locy=targety\n",
    "            res+='!'\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    position = dict()\n",
    "    for x, row in enumerate([\"abcde\", \"fghij\", \"klmno\", \"pqrst\", \"uvwxy\", \"z\"]):\n",
    "        for y, c in enumerate(row):\n",
    "            position[c] = (x, y)\n",
    "\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        ret = ''\n",
    "        src = 'a'\n",
    "        for dest in target:\n",
    "            if src != dest:\n",
    "                dest1 = dest\n",
    "                if src == 'z':\n",
    "                    ret += 'U'\n",
    "                    src = 'u'\n",
    "                elif dest == 'z':\n",
    "                    dest1 = 'u'\n",
    "                else:\n",
    "                    pass\n",
    "                src_x, src_y = self.position[src]\n",
    "                dest_x, dest_y = self.position[dest1]\n",
    "                dx = 'D' if src_x < dest_x else 'U'\n",
    "                dy = 'R' if src_y < dest_y else 'L'\n",
    "                ret += dx * abs(src_x - dest_x) + dy * abs(src_y - dest_y)\n",
    "                if dest == 'z':\n",
    "                    ret += 'D'\n",
    "\n",
    "            ret += '!'\n",
    "            src = dest\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        ans=''\n",
    "        target='a'+target\n",
    "        f={}\n",
    "        for i in range(26):\n",
    "            x=chr(i+97)\n",
    "            f[x]=[i%5,i//5]\n",
    "        for i in range(1,len(target)):\n",
    "            x=target[i-1]\n",
    "            y=target[i]\n",
    "            if y==x:\n",
    "                ans+='!'\n",
    "                continue\n",
    "            a=f[y][0]-f[x][0]\n",
    "            b=f[y][1]-f[x][1]\n",
    "            if y=='z':\n",
    "                \n",
    "                if a>0:\n",
    "                    for i in range(a):\n",
    "                        ans+='R'\n",
    "                elif a<0:\n",
    "                    for i in range(-1*a):\n",
    "                        ans+='L'\n",
    "                if b>0:\n",
    "                    for i in range(b):\n",
    "                        ans+='D'\n",
    "                elif b<0:\n",
    "                    for i in range(-1*b):\n",
    "                        ans+='U'\n",
    "                ans+='!'\n",
    "                continue\n",
    "\n",
    "            if b>0:\n",
    "                for i in range(b):\n",
    "                    ans+='D'\n",
    "            elif b<0:\n",
    "                for i in range(-1*b):\n",
    "                    ans+='U'\n",
    "            \n",
    "            if a>0:\n",
    "                for i in range(a):\n",
    "                    ans+='R'\n",
    "            elif a<0:\n",
    "                for i in range(-1*a):\n",
    "                    ans+='L'\n",
    "            ans+='!'\n",
    "        return ans\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        ans = []\n",
    "        prex = prey = 0\n",
    "        for c in target:\n",
    "            nx, ny = divmod(ord(c) - ord('a'), 5)  # 目标位置\n",
    "            v = \"UD\"[nx > prex] * abs(nx - prex)  # 竖直\n",
    "            h = \"LR\"[ny > prey] * abs(ny - prey)  # 水平\n",
    "            ans.append((v + h if c != 'z' else h + v) + \"!\")\n",
    "            prex, prey = nx, ny\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        #将每一个位置都坐标化，初始坐标是(0,0)\n",
    "        locx=0\n",
    "        locy=0\n",
    "        res=\"\"\n",
    "        for i in target:\n",
    "            #求得目标位置的坐标\n",
    "            temp=ord(i)-ord('a')\n",
    "            targetx=temp%5\n",
    "            targety=temp//5\n",
    "            if targetx<locx:\n",
    "                res+='L'*(locx-targetx)\n",
    "            if targety<locy:\n",
    "                res+='U'*(locy-targety)\n",
    "            if targety>locy:\n",
    "                res+='D'*(targety-locy)\n",
    "            if targetx>locx:\n",
    "                res+='R'*(targetx-locx)\n",
    "            locx=targetx\n",
    "            locy=targety\n",
    "            res+='!'\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        d={\"a\":(0,0),\"b\":(0,1),\"c\":(0,2),\"d\":(0,3),\"e\":(0,4),\n",
    "        \"f\":(1,0),\"g\":(1,1),\"h\":(1,2),\"i\":(1,3),\"j\":(1,4),\n",
    "        \"k\":(2,0),\"l\":(2,1),\"m\":(2,2),\"n\":(2,3),\"o\":(2,4),\n",
    "        \"p\":(3,0),\"q\":(3,1),\"r\":(3,2),\"s\":(3,3),\"t\":(3,4),\n",
    "        \"u\":(4,0),\"v\":(4,1),\"w\":(4,2),\"x\":(4,3),\"y\":(4,4),\n",
    "        \"z\":(5,0)}\n",
    "        ans=\"\"\n",
    "        pr,pc=0,0\n",
    "        for c in target:\n",
    "            cr,cc=d[c]\n",
    "            if pr==5:\n",
    "                if pr<cr:\n",
    "                    ans+=\"D\"*(cr-pr)\n",
    "                else:\n",
    "                    ans+=\"U\"*(pr-cr)\n",
    "                if pc<cc:\n",
    "                    ans+=\"R\"*(cc-pc)\n",
    "                else:\n",
    "                    ans+=\"L\"*(pc-cc)\n",
    "            else:\n",
    "                if pc<cc:\n",
    "                    ans+=\"R\"*(cc-pc)\n",
    "                else:\n",
    "                    ans+=\"L\"*(pc-cc)\n",
    "                if pr<cr:\n",
    "                    ans+=\"D\"*(cr-pr)\n",
    "                else:\n",
    "                    ans+=\"U\"*(pr-cr)\n",
    "            ans+=\"!\"\n",
    "            pr,pc=cr,cc\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        ans = ''\n",
    "        x_n = 0\n",
    "        y_n = 0\n",
    "        for i in range(len(target)):\n",
    "            target_c = target[i]\n",
    "            y = (ord(target_c) - ord('a')) % 5\n",
    "            x = (ord(target_c) - ord('a')) // 5\n",
    "            if x == 5:\n",
    "                if y > y_n:\n",
    "                    ans += 'R' * abs(y - y_n)\n",
    "                elif y < y_n:\n",
    "                    ans += 'L' * abs(y - y_n)\n",
    "                if x > x_n:\n",
    "                    ans += 'D' * abs(x - x_n)\n",
    "                elif x < x_n:\n",
    "                    ans += 'U' * abs(x - x_n)\n",
    "\n",
    "            else:\n",
    "                if x > x_n:\n",
    "                    ans += 'D' * abs(x - x_n)\n",
    "                elif x < x_n:\n",
    "                    ans += 'U' * abs(x - x_n)\n",
    "                if y > y_n:\n",
    "                    ans += 'R' * abs(y - y_n)\n",
    "                elif y < y_n:\n",
    "                    ans += 'L' * abs(y - y_n)\n",
    "            ans += '!'\n",
    "            x_n = x\n",
    "            y_n = y\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        now_point = [0, 0]\n",
    "        res_list = []\n",
    "        aim_str = \"abcdefghijklmnopqrstuvwxyz\"\n",
    "        for i in range(len(target)):\n",
    "            index = aim_str.find(target[i])\n",
    "            new_point = [index // 5 , index % 5]\n",
    "            x_distance = new_point[0] - now_point[0]\n",
    "            y_distance = new_point[1] - now_point[1]\n",
    "            if x_distance == 0 and y_distance == 0:\n",
    "                res_list.append(\"!\")\n",
    "                now_point = new_point\n",
    "                continue\n",
    "            if now_point[0] == 5:\n",
    "                if x_distance > 0:\n",
    "                    for _ in range(x_distance):\n",
    "                        res_list.append(\"D\")\n",
    "                if x_distance < 0:\n",
    "                    for _ in range(abs(x_distance)):\n",
    "                        res_list.append(\"U\")\n",
    "                if y_distance > 0:\n",
    "                    for _ in range(y_distance):\n",
    "                        res_list.append(\"R\")\n",
    "                if y_distance < 0:\n",
    "                    for _ in range(abs(y_distance)):\n",
    "                        res_list.append(\"L\")\n",
    "            else:\n",
    "                if y_distance > 0:\n",
    "                    for _ in range(y_distance):\n",
    "                        res_list.append(\"R\")\n",
    "                if y_distance < 0:\n",
    "                    for _ in range(abs(y_distance)):\n",
    "                        res_list.append(\"L\")\n",
    "                if x_distance > 0:\n",
    "                    for _ in range(x_distance):\n",
    "                        res_list.append(\"D\")\n",
    "                if x_distance < 0:\n",
    "                    for _ in range(abs(x_distance)):\n",
    "                        res_list.append(\"U\")\n",
    "            res_list.append(\"!\")\n",
    "            now_point = new_point\n",
    "        return \"\".join(res_list)\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        cx = cy = 0\n",
    "        res = []\n",
    "        for c in target:\n",
    "            c = ord(c) - ord('a')\n",
    "            nx = c // 5\n",
    "            ny = c % 5\n",
    "            if nx < cx:\n",
    "                res.append('U' * (cx - nx))\n",
    "            if ny < cy:\n",
    "                res.append('L' * (cy - ny))\n",
    "            if nx > cx:\n",
    "                res.append('D' * (nx - cx))\n",
    "            if ny > cy:\n",
    "                res.append('R' * (ny - cy))\n",
    "            res.append('!')\n",
    "            cx = nx\n",
    "            cy = ny\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        def pos(letter):\n",
    "            v = ord(letter) - ord('a')\n",
    "            return divmod(v, 5)\n",
    "        ans = \"\"\n",
    "        x, y = 0, 0\n",
    "        for let in target:\n",
    "            cx, cy = pos(let)\n",
    "            tmp = []\n",
    "            if cx > x:\n",
    "                tmp += ['D'] * (cx - x) \n",
    "            elif cx < x:\n",
    "                tmp += ['U'] * (x - cx)\n",
    "            \n",
    "            if cy > y:\n",
    "                tmp += ['R'] * (cy - y)\n",
    "            elif cy < y:\n",
    "                tmp += ['L'] * (y - cy)\n",
    "            \n",
    "            #UUL, => ULU\n",
    "            #UULLL => ULLLU\n",
    "            if let == 'z':\n",
    "               #swap last U with last L \n",
    "                lu, ll = -1, -1\n",
    "                for i, c in enumerate(tmp):\n",
    "                    if c == 'D':\n",
    "                        lu = i\n",
    "                    if c == 'L':\n",
    "                        ll = i\n",
    "                if lu != -1 and ll != -1:\n",
    "                    # print(f'tmp={tmp}')\n",
    "                    tmp[lu], tmp[ll] = tmp[ll], tmp[lu]\n",
    "            # if x == 5:\n",
    "                #always move by x first\n",
    "\n",
    "            tmp.append('!')\n",
    "            ans += \"\".join(tmp)\n",
    "            x, y = cx, cy\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        x, y = 0, 0\n",
    "        ans = []\n",
    "        for let in target:\n",
    "            cx, cy = divmod(ord(let) - ord('a'), 5)\n",
    "            v = \"UD\"[cx > x] * abs(cx - x)\n",
    "            h = \"LR\"[cy > y] * abs(cy - y)\n",
    "            ans.append((v + h) if let != 'z' else (h + v))\n",
    "            ans.append('!')\n",
    "            x, y = cx, cy\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        characters = (\n",
    "            'a', 'b', 'c', 'd', 'e',\n",
    "            'f', 'g', 'h', 'i', 'j',\n",
    "            'k', 'l', 'm', 'n', 'o',\n",
    "            'p', 'q', 'r', 's', 't',\n",
    "            'u', 'v', 'w', 'x', 'y',\n",
    "            'z')\n",
    "        board = (\n",
    "            (0, 1, 2, 3, 4),\n",
    "            (5, 6, 7, 8, 9), \n",
    "            (10, 11, 12, 13, 14), \n",
    "            (15, 16, 17, 18, 19), \n",
    "            (20, 21, 22, 23, 24), \n",
    "            (25, 26, 27, 28, 29)\n",
    "        )\n",
    "\n",
    "        current = [0, 0]\n",
    "        target = tuple(map(lambda c: characters.index(c), target))\n",
    "        control = list()\n",
    "        for t in target:\n",
    "            y = (board[current[1]][1] - board[t // 5][1]) // 5\n",
    "            x = t % 5 - current[0] % 5\n",
    "\n",
    "            if y > 0:\n",
    "                control.append('U' * y)\n",
    "            if x < 0:\n",
    "                control.append('L' * abs(x))\n",
    "            if y < 0:\n",
    "                control.append('D' * abs(y))\n",
    "            if x > 0:\n",
    "                control.append('R' * x)\n",
    "            \n",
    "            control.append('!')\n",
    "            current[0], current[1] = current[0] + x, current[1] - y\n",
    "        return ''.join(control)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        ans = []\n",
    "        x = y = 0\n",
    "        for c in target:\n",
    "            nx, ny = divmod(ord(c) - ord('a'), 5)  # 目标位置\n",
    "            v = \"UD\"[nx > x] * abs(nx - x)  # 竖直\n",
    "            h = \"LR\"[ny > y] * abs(ny - y)  # 水平\n",
    "            ans.append((v + h if c != 'z' else h + v) + \"!\")\n",
    "            x, y = nx, ny\n",
    "        return ''.join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        cx = cy = 0\n",
    "        res = []\n",
    "        for c in target:\n",
    "            c = ord(c) - ord('a')\n",
    "            nx = c // 5\n",
    "            ny = c % 5\n",
    "            if nx < cx:\n",
    "                res.append('U' * (cx - nx))\n",
    "            if ny < cy:\n",
    "                res.append('L' * (cy - ny))\n",
    "            if nx > cx:\n",
    "                res.append('D' * (nx - cx))\n",
    "            if ny > cy:\n",
    "                res.append('R' * (ny - cy))\n",
    "            res.append('!')\n",
    "            cx = nx\n",
    "            cy = ny\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        res = []\n",
    "        x = y = 0\n",
    "        for ch in target:\n",
    "            nx,ny = divmod(ord(ch) - ord('a'),5)\n",
    "            v = \"UD\"[nx > x] * abs(nx-x)\n",
    "            h = \"LR\"[ny > y] * abs(ny-y)\n",
    "            res.append((v + h if ch != 'z' else h + v) + \"!\")\n",
    "            x = nx\n",
    "            y = ny\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        current = 0\n",
    "        res = list()\n",
    "        for t in [ord(t) - 97 for t in target]:\n",
    "            y = ((current - current % 5 + 4) - (t - t % 5 + 4)) // 5\n",
    "            x = t % 5 - current % 5\n",
    "\n",
    "            if y > 0:\n",
    "                res.append('U' * y)\n",
    "            if x < 0:\n",
    "                res.append('L' * abs(x))\n",
    "            if y < 0:\n",
    "                res.append('D' * abs(y))\n",
    "            if x > 0:\n",
    "                res.append('R' * x)\n",
    "            \n",
    "            res.append('!')\n",
    "            current = t\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        d={\"a\":(0,0),\"b\":(0,1),\"c\":(0,2),\"d\":(0,3),\"e\":(0,4),\n",
    "        \"f\":(1,0),\"g\":(1,1),\"h\":(1,2),\"i\":(1,3),\"j\":(1,4),\n",
    "        \"k\":(2,0),\"l\":(2,1),\"m\":(2,2),\"n\":(2,3),\"o\":(2,4),\n",
    "        \"p\":(3,0),\"q\":(3,1),\"r\":(3,2),\"s\":(3,3),\"t\":(3,4),\n",
    "        \"u\":(4,0),\"v\":(4,1),\"w\":(4,2),\"x\":(4,3),\"y\":(4,4),\n",
    "        \"z\":(5,0)}\n",
    "        ans=\"\"\n",
    "        pr,pc=0,0\n",
    "        for c in target:\n",
    "            cr,cc=d[c]\n",
    "            if pr>cr:\n",
    "                ans+=\"U\"*(pr-cr)\n",
    "            if cc<pc:\n",
    "                ans+=\"L\"*(pc-cc)\n",
    "            if pr<cr:\n",
    "                ans+=\"D\"*(cr-pr)\n",
    "            if cc>pc:\n",
    "                ans+=\"R\"*(cc-pc)\n",
    "            ans+=\"!\"\n",
    "            pr,pc=cr,cc\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        ans = []\n",
    "        x = y = 0\n",
    "        for c in target:\n",
    "            nx, ny = divmod(ord(c) - ord('a'), 5)  # 目标位置\n",
    "            v = \"UD\"[nx > x] * abs(nx - x)  # 竖直\n",
    "            h = \"LR\"[ny > y] * abs(ny - y)  # 水平\n",
    "            ans.append((v + h if c != 'z' else h + v) + \"!\")\n",
    "            x, y = nx, ny\n",
    "        return ''.join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        nowr=0\n",
    "        nowc=0\n",
    "        res=''\n",
    "        for i in target:\n",
    "            r,c=divmod(ord(i)-97,5)\n",
    "            if c-nowc>0:\n",
    "                if r-nowr>0:\n",
    "                    res=f'{res}{\"D\"*(r-nowr)}'\n",
    "                else:\n",
    "                    res=f'{res}{\"U\"*(nowr-r)}'\n",
    "                res=f'{res}{\"R\"*(c-nowc)}'\n",
    "            else:\n",
    "                res=f'{res}{\"L\"*(nowc-c)}'\n",
    "                if r-nowr>0:\n",
    "                    res=f'{res}{\"D\"*(r-nowr)}'\n",
    "                else:\n",
    "                    res=f'{res}{\"U\"*(nowr-r)}'\n",
    "\n",
    "            res=f'{res}!'\n",
    "            nowr=r\n",
    "            nowc=c\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        x0,y0 = 0, 0\n",
    "        self.ans = ''\n",
    "        def x(x0: int,x1: int):\n",
    "            while x0 != x1:\n",
    "                if x0 > x1:\n",
    "                    self.ans += 'U'\n",
    "                    x0 -= 1\n",
    "                else:\n",
    "                    self.ans += 'D'\n",
    "                    x0 += 1\n",
    "            return x0,x1\n",
    "        def y(y0: int, y1: int):\n",
    "            while y0 != y1:\n",
    "                if y0 > y1:\n",
    "                    self.ans += 'L'\n",
    "                    y0 -= 1\n",
    "                else:\n",
    "                    self.ans += 'R'\n",
    "                    y0 += 1\n",
    "            return y0,y1\n",
    "        for t in target:\n",
    "            x1,y1 = (ord(t)-97)//5,(ord(t)-97)%5\n",
    "            if x0 == 5:\n",
    "                x0,x1 = x(x0,x1)\n",
    "                y0,y1 = y(y0,y1)\n",
    "            else:\n",
    "                y0,y1 = y(y0,y1)\n",
    "                x0,x1 = x(x0,x1)\n",
    "            self.ans += '!'\n",
    "        return self.ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        d = {}\n",
    "        for i in range(5):\n",
    "            for j in range(5):\n",
    "                d[chr(ord('a') + i * 5 + j)] = (i, j)\n",
    "        d['z'] = (5, 0)\n",
    "        result = []\n",
    "        cx, cy = 0, 0\n",
    "        for each in target:\n",
    "            target_x, target_y = d[each]\n",
    "            dx, dy = target_x - cx, target_y - cy\n",
    "            if cx == 5 and cy == 0 and dy > 0:\n",
    "                result += ['U']\n",
    "                dx += 1\n",
    "            if dy > 0:\n",
    "                result += ['R' for _ in range(dy)]\n",
    "            else:\n",
    "                result += ['L' for _ in range(-dy)]\n",
    "            if dx > 0:\n",
    "                result += ['D' for _ in range(dx)]\n",
    "            else:\n",
    "                result += ['U' for _ in range(-dx)]\n",
    "            result.append('!')\n",
    "            cx, cy = target_x, target_y\n",
    "        return ''.join(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        cx = cy = 0\n",
    "        res = []\n",
    "        for c in target:\n",
    "            c = ord(c) - ord('a')\n",
    "            nx = c // 5\n",
    "            ny = c % 5\n",
    "            if nx < cx:\n",
    "                res.append('U' * (cx - nx))\n",
    "            if ny < cy:\n",
    "                res.append('L' * (cy - ny))\n",
    "            if nx > cx:\n",
    "                res.append('D' * (nx - cx))\n",
    "            if ny > cy:\n",
    "                res.append('R' * (ny - cy))\n",
    "            res.append('!')\n",
    "            cx = nx\n",
    "            cy = ny\n",
    "        return ''.join(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        x=0\n",
    "        y=0\n",
    "        ans=''\n",
    "        myc='#'\n",
    "        for c in target:\n",
    "            xx=(ord(c)-ord('a'))//5\n",
    "            yy=(ord(c)-ord('a'))%5\n",
    "            if xx==5:\n",
    "                if yy-y>0:\n",
    "                    myc='R'\n",
    "                if yy-y<0:\n",
    "                    myc='L'\n",
    "                ans+=myc*abs(y-yy)\n",
    "                y=yy\n",
    "            if xx-x>0:\n",
    "                myc='D'\n",
    "            if xx-x<0:\n",
    "                myc='U'\n",
    "            #for i in range(abs(x-xx)):\n",
    "            ans+=myc*abs(x-xx)\n",
    "            if yy-y>0:\n",
    "                myc='R'\n",
    "            if yy-y<0:\n",
    "                myc='L'\n",
    "            ans+=myc*abs(y-yy)\n",
    "            ans+='!'\n",
    "            x=xx\n",
    "            y=yy\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        def pos(letter):\n",
    "            v = ord(letter) - ord('a')\n",
    "            return divmod(v, 5)\n",
    "        ans = []\n",
    "        x, y = 0, 0\n",
    "        for let in target:\n",
    "            cx, cy = pos(let)\n",
    "            if cy < y:\n",
    "                ans.append('L' * (y - cy))\n",
    "            if cx < x:\n",
    "                ans.append('U' * (x - cx))\n",
    "            if cx > x:\n",
    "                ans.append('D' * (cx - x))\n",
    "            if cy > y:\n",
    "                ans.append('R' * (cy - y))\n",
    "            x, y = cx, cy\n",
    "            ans.append('!')\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        def pos(letter):\n",
    "            v = ord(letter) - ord('a')\n",
    "            return divmod(v, 5)\n",
    "        ans = []\n",
    "        x, y = 0, 0\n",
    "        for let in target:\n",
    "            cx, cy = pos(let)\n",
    "            if cy < y:\n",
    "                ans.append('L' * (y - cy))\n",
    "            if cx > x:\n",
    "                ans.append('D' * (cx - x))\n",
    "            if cx < x:\n",
    "                ans.append('U' * (x - cx))\n",
    "            if cy > y:\n",
    "                ans.append('R' * (cy - y))\n",
    "            x, y = cx, cy\n",
    "            ans.append('!')\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "\n",
    "        current = 0\n",
    "        res = list()\n",
    "\n",
    "        for t in map(lambda c: ord(c) - 97, target):\n",
    "            y = (current - t + t % 5 - current % 5) // 5\n",
    "            x = t % 5 - current % 5\n",
    "\n",
    "            if y > 0:\n",
    "                res.append('U' * y)\n",
    "            if x < 0:\n",
    "                res.append('L' * abs(x))\n",
    "            if y < 0:\n",
    "                res.append('D' * abs(y))\n",
    "            if x > 0:\n",
    "                res.append('R' * x)\n",
    "            \n",
    "            res.append('!')\n",
    "            current = t\n",
    "        \n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        m = []\n",
    "        for c in range(26):\n",
    "            m.append((c // 5, c % 5))\n",
    "            \n",
    "        cur = (0, 0)\n",
    "        ans = ''\n",
    "        for c in target:\n",
    "            id = ord(c) - ord('a')\n",
    "            \n",
    "            if id == 25 and cur != (5, 0):\n",
    "                pos = m[ord('u') - ord('a')]\n",
    "                for i in range(abs(pos[0] - cur[0])):\n",
    "                    ans += 'D' if pos[0] > cur[0] else 'U'\n",
    "                for i in range(abs(pos[1] - cur[1])):\n",
    "                    ans += 'R' if pos[1] > cur[1] else 'L'\n",
    "                cur = pos    \n",
    "                    \n",
    "            pos = m[id]\n",
    "            \n",
    "            for i in range(abs(pos[0] - cur[0])):\n",
    "                ans += 'D' if pos[0] > cur[0] else 'U'\n",
    "            for i in range(abs(pos[1] - cur[1])):\n",
    "                ans += 'R' if pos[1] > cur[1] else 'L'\n",
    "                \n",
    "            ans += '!'\n",
    "            cur = pos\n",
    "        return ans            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        current = 0\n",
    "        res = list()\n",
    "\n",
    "        for t in map(lambda c: ord(c) - 97, target):\n",
    "            y = (current - t + t % 5 - current % 5) // 5\n",
    "            x = t % 5 - current % 5\n",
    "\n",
    "            if y > 0:\n",
    "                res.append('U' * y)\n",
    "            if x < 0:\n",
    "                res.append('L' * abs(x))\n",
    "            if y < 0:\n",
    "                res.append('D' * abs(y))\n",
    "            if x > 0:\n",
    "                res.append('R' * x)\n",
    "            \n",
    "            res.append('!')\n",
    "            current = t\n",
    "        \n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        x, y = 0, 0\n",
    "        ans = []\n",
    "        for let in target:\n",
    "            cx, cy = divmod(ord(let) - ord('a'), 5)\n",
    "            if cy < y:\n",
    "                ans.append('L' * (y - cy))\n",
    "            if cx < x:\n",
    "                ans.append('U' * (x - cx))\n",
    "            if cx > x:\n",
    "                ans.append('D' * (cx - x))\n",
    "            if cy > y:\n",
    "                ans.append('R' * (cy - y))\n",
    "            x, y = cx, cy\n",
    "            ans.append('!')\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        ans = ''\n",
    "        def pos(c):\n",
    "            n = ord(c) - ord('a')\n",
    "            return n // 5, n % 5\n",
    "        def move(x1, y1, x2, y2):\n",
    "            #print(x1, y1, x2, y2)\n",
    "            s = ''\n",
    "            if x2 > x1:\n",
    "                if y2 > y1:\n",
    "                    for i in range(y2 - y1):\n",
    "                        s += 'R'\n",
    "                else:\n",
    "                    for i in range(y1 - y2):\n",
    "                        s += 'L'\n",
    "                if x2 > x1:\n",
    "                    for i in range(x2 - x1):\n",
    "                        s += 'D'\n",
    "                else:\n",
    "                    for i in range(x1 - x2):\n",
    "                        s += 'U'\n",
    "            else:\n",
    "                if x2 > x1:\n",
    "                    for i in range(x2 - x1):\n",
    "                        s += 'D'\n",
    "                else:\n",
    "                    for i in range(x1 - x2):\n",
    "                        s += 'U'\n",
    "                if y2 > y1:\n",
    "                    for i in range(y2 - y1):\n",
    "                        s += 'R'\n",
    "                else:\n",
    "                    for i in range(y1 - y2):\n",
    "                        s += 'L'\n",
    "\n",
    "\n",
    "\n",
    "            return s\n",
    "        x1, y1 = 0, 0\n",
    "        for i in range(len(target)):\n",
    "            x2, y2 = pos(target[i])\n",
    "            ans += move(x1, y1, x2, y2)\n",
    "            ans += '!'\n",
    "            x1 = x2\n",
    "            y1 = y2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        # board = [\"abcde\", \"fghij\", \"klmno\", \"pqrst\", \"uvwxy\", \"z\"]\n",
    "        # for i in target:\n",
    "        pre = 'a'\n",
    "        res = ''\n",
    "        def zuobiao(ch):\n",
    "            cha = ord(ch) - ord('a')\n",
    "            x =  cha // 5 \n",
    "            y = cha % 5\n",
    "            return x,y  \n",
    "        \n",
    "        for i in target:\n",
    "            xi,yi = zuobiao(i)\n",
    "            xp,yp = zuobiao(pre)\n",
    "            if (xi,yi) == (xp,yp):\n",
    "                res += '!'\n",
    "                continue \n",
    "            if xp < xi:\n",
    "                if xi == 5:\n",
    "                    res += (xi-xp-1)*'D'\n",
    "                else:\n",
    "                    res += (xi-xp)*'D'\n",
    "            if xp > xi:\n",
    "                res += (xp-xi)*'U'\n",
    "            if yp < yi:\n",
    "                res += (yi-yp)*'R'\n",
    "            if yp > yi:\n",
    "                res += (yp-yi)*'L'\n",
    "            if xi == 5:\n",
    "                res += 'D'\n",
    "            res += '!'\n",
    "            pre = i \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    position = dict()\n",
    "    for x, row in enumerate([\"abcde\", \"fghij\", \"klmno\", \"pqrst\", \"uvwxy\", \"z\"]):\n",
    "        for y, c in enumerate(row):\n",
    "            position[c] = (x, y)\n",
    "\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        ret = ''\n",
    "        src = 'a'\n",
    "        for dest in target:\n",
    "            ret += self.move(src, dest) + '!'\n",
    "            src = dest\n",
    "        print(ret)\n",
    "        return ret\n",
    "\n",
    "    def move(self, src, dest):\n",
    "        if src == dest:\n",
    "            ret = ''\n",
    "        elif src == 'z':\n",
    "            ret = 'U' + self.move('u', dest)\n",
    "        elif dest == 'z':\n",
    "            ret = self.move(src, 'u') + 'D'\n",
    "        else:\n",
    "            src_x, src_y = self.position[src]\n",
    "            dest_x, dest_y = self.position[dest]\n",
    "            dx = 'D' if src_x < dest_x else 'U'\n",
    "            dy = 'R' if src_y < dest_y else 'L'\n",
    "            ret = dx * abs(src_x - dest_x) + dy * abs(src_y - dest_y)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        ans = []\n",
    "        x = y = 0\n",
    "        for c in target:\n",
    "            nx, ny = divmod(ord(c) - ord('a'), 5)  # 目标位置\n",
    "            v = \"UD\"[nx > x] * abs(nx - x)  # 竖直\n",
    "            h = \"LR\"[ny > y] * abs(ny - y)  # 水平\n",
    "            ans.append((v + h if c != 'z' else h + v) + \"!\")\n",
    "            x, y = nx, ny\n",
    "        return ''.join(ans)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        r = 6\n",
    "        c = 5\n",
    "        getPos = lambda x: ((ord(x) - 97) // c, (ord(x) - 97) % c)\n",
    "        res = []\n",
    "        prev = 'a'\n",
    "        # p_i, p_j = 0, 0\n",
    "        for alpha in target:\n",
    "            if alpha == prev:\n",
    "                res.append('!')\n",
    "            else:\n",
    "                if prev != 'z' and alpha != 'z':\n",
    "                    prev_i, prev_j = getPos(prev)\n",
    "                    cur_i, cur_j = getPos(alpha)\n",
    "\n",
    "                    di = cur_i - prev_i\n",
    "                    dj = cur_j - prev_j\n",
    "\n",
    "                    if di >= 0:\n",
    "                        res.append('D' * di)\n",
    "                    else:\n",
    "                        res.append('U' * (-di))\n",
    "                    \n",
    "                    if dj >= 0:\n",
    "                        res.append('R' * dj)\n",
    "                    else:\n",
    "                        res.append('L' * (-dj))\n",
    "                elif prev == 'z':\n",
    "                    prev_i, prev_j = getPos(prev)\n",
    "                    cur_i, cur_j = getPos(alpha)\n",
    "\n",
    "                    di = cur_i - prev_i\n",
    "                    dj = cur_j - prev_j\n",
    "\n",
    "\n",
    "                    if di >= 0:\n",
    "                        res.append('D' * di)\n",
    "                    else:\n",
    "                        res.append('U' * (-di))\n",
    "\n",
    "                    if dj >= 0:\n",
    "                        res.append('R' * dj)\n",
    "                    else:\n",
    "                        res.append('L' * (-dj))\n",
    "\n",
    "                    \n",
    "                else:\n",
    "                    prev_i, prev_j = getPos(prev)\n",
    "                    cur_i, cur_j = getPos(alpha)\n",
    "\n",
    "                    di = cur_i - prev_i\n",
    "                    dj = cur_j - prev_j\n",
    "\n",
    "                    if dj >= 0:\n",
    "                        res.append('R' * dj)\n",
    "                    else:\n",
    "                        res.append('L' * (-dj))\n",
    "\n",
    "                    if di >= 0:\n",
    "                        res.append('D' * di)\n",
    "                    else:\n",
    "                        res.append('U' * (-di))\n",
    "                    \n",
    "\n",
    "\n",
    "                res.append('!')\n",
    "\n",
    "            prev = alpha\n",
    "                    \n",
    "\n",
    "\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        i = j = 0\n",
    "        ans = []\n",
    "        for c in target:\n",
    "            v = ord(c) - ord('a')\n",
    "            x, y = v // 5, v % 5\n",
    "            while j > y:\n",
    "                j -= 1\n",
    "                ans.append('L')\n",
    "            while i > x:\n",
    "                i -= 1\n",
    "                ans.append('U')\n",
    "            while j < y:\n",
    "                j += 1\n",
    "                ans.append('R')\n",
    "            while i < x:\n",
    "                i += 1\n",
    "                ans.append('D')\n",
    "            ans.append('!')\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphabetBoardPath(self, target: str) -> str:\n",
    "        board = ['abcde', 'fghij', 'klmno', 'pqrst', 'uvwxy', 'z']\n",
    "        dic = {}\n",
    "        res = ''\n",
    "        for i, word in enumerate(board):\n",
    "            for j in range(len(word)):\n",
    "                dic[word[j]] = (i, j)\n",
    "        i = j = 0\n",
    "        for ch in target:\n",
    "            x, y = dic[ch]\n",
    "            while j > y:\n",
    "                j -= 1\n",
    "                res += 'L'\n",
    "            while i > x:\n",
    "                i -= 1\n",
    "                res += 'U'\n",
    "            while j < y:\n",
    "                j += 1\n",
    "                res += 'R'\n",
    "            while i < x:\n",
    "                i += 1\n",
    "                res += 'D'\n",
    "            res += '!'\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
